package edu.whu.rose.clock.kps.algorithm.cbes;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import edu.whu.rose.clock.kps.algorithm.SearchAlgorithm;
import edu.whu.rose.clock.kps.algorithm.banks1.SPVertex;
import edu.whu.rose.clock.kps.datastruct.SimpleAnswer;
import edu.whu.rose.clock.kps.datastruct.SimpleMatchedSubgraph;
import edu.whu.rose.clock.kps.datastruct.SimpleSubgraphVertex;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;
import edu.whu.rose.clock.util.priorityqueue.FibonacciHeapPQ;
import edu.whu.rose.clock.util.priorityqueue.UnderflowException;

public class ConcurrentBackwardExpandingSearchWithEagerness extends SearchAlgorithm {

	private int groupNum;

	private HashMap<Integer, SimpleMatchedSubgraph> matched_subgraphs;

	private HashSet<SimpleSubgraphVertex> all_matched_vertexes;
	private HashMap<Integer, HashMap<Integer, Integer>> matched_vertexes_in_subgraph;
	private FibonacciHeapPQ<DijkstraIteratorInSubgraph> iterator_heap;

	public ConcurrentBackwardExpandingSearchWithEagerness(
			SimpleMatchedSubgraph[] matched_subgraphs) {
		groupNum = matched_subgraphs[0].groupNum();
		this.matched_subgraphs = new HashMap<Integer, SimpleMatchedSubgraph>();
		for (int i = 0; i < matched_subgraphs.length; i++) {
			this.matched_subgraphs.put(new Integer(matched_subgraphs[i]
					.getSubgraphID()), matched_subgraphs[i]);
		}
	}

	public void init() {
		all_matched_vertexes = unionSubgraphVertexes();
		iterator_heap = new FibonacciHeapPQ<DijkstraIteratorInSubgraph>();
		Iterator<SimpleSubgraphVertex> li = all_matched_vertexes.iterator();
		while (li.hasNext()) {
			SimpleSubgraphVertex sv = li.next();
			DijkstraIteratorInSubgraph di = new DijkstraIteratorInSubgraph(
					matched_subgraphs.get(new Integer(sv.getSubgraph_id()))
							.getSubgraphMatrix(), sv);
			iterator_heap.enqueue(di);
		}
	}

	public SimpleAnswer[] process(int k) {
		int size = 0;
		SimpleAnswer[] topk = new SimpleAnswer[k];
		
		HashMap<Integer, HashMap<Integer, ExpandableIntArray[]>> nodeListsInAllSubgraphs = 
			new HashMap<Integer, HashMap<Integer, ExpandableIntArray[]>>();
		HashMap<Integer, HashMap<Integer, HashMap<Integer, Integer>>> predecessorsInAllSubgraphs = 
			new HashMap<Integer, HashMap<Integer, HashMap<Integer, Integer>>>();
		Iterator<Integer> it = matched_subgraphs.keySet().iterator();
		while (it.hasNext()) {
			Integer I = it.next();
			
			// initialize the predecessors
			
			HashMap<Integer, HashMap<Integer, Integer>> predecessors = new HashMap<Integer, HashMap<Integer, Integer>>();
			
			Iterator<Integer> it2 = matched_vertexes_in_subgraph.get(I).keySet().iterator();
			while (it2.hasNext()) {
				Integer v = it2.next();
				predecessors.put(v, new HashMap<Integer, Integer>());
			}
			
			nodeListsInAllSubgraphs.put(I, 
					new HashMap<Integer, ExpandableIntArray[]>());
			predecessorsInAllSubgraphs.put(I, 
					predecessors);
		}

		// begin to search
		while (!iterator_heap.isEmpty()) {
			try {
				// get the iterator with minimum next value from the heap
				DijkstraIteratorInSubgraph diis = iterator_heap.dequeueMin();  // iterator
																				// with
																				// minimum
																				// next
																				// value
				
				double dis = diis.peek();
				HashMap<Integer, ArrayList<DijkstraIteratorInSubgraph>> spvertexes = 
					new HashMap<Integer, ArrayList<DijkstraIteratorInSubgraph>>();
				for (int i = 1; i < groupNum; i++) {
					spvertexes.put(new Integer(i), new ArrayList<DijkstraIteratorInSubgraph>());
				}
				while (!iterator_heap.isEmpty()) {
					if (dis == iterator_heap.findMin().peek()) {
						DijkstraIteratorInSubgraph temp = iterator_heap.dequeueMin();
						int subgraph = temp.getSource().getSubgraph_id();
						int vertex = temp.getSource().getVertex_id();
						Integer num = 
							matched_vertexes_in_subgraph.get(new Integer(subgraph)).get(new Integer(vertex));
						spvertexes.get(num).add(temp);
					}
					else {
						break;
					}
				}
				
				for (int j = groupNum - 1; j > 0; j--) {
					ArrayList<DijkstraIteratorInSubgraph> list = spvertexes.get(new Integer(j));
					Iterator<DijkstraIteratorInSubgraph> dit = list.iterator();
					while (dit.hasNext()) {
						DijkstraIteratorInSubgraph di = dit.next();
						
						SimpleSubgraphVertex source = di.getSource();                // source
												// of
												// this
												// iterator
						int vid = source.getVertex_id();                            // matched
												// vertex
												// of
												// this
												// source
						int gid = source.getSubgraph_id();                          // subgraph
												// of
												// this
												// source
						SPVertex spv = di.next();                                    // shortest
												// path
												// from
												// source
						int root = spv.getID();                                      // vertex
												// in
												// the
												// end
												// of
												// this
												// path
						
						Integer SG = new Integer(gid);
						Integer R = new Integer(root);
						
						SimpleMatchedSubgraph matched_subgraph = matched_subgraphs.get(SG);
						
						HashMap<Integer, ExpandableIntArray[]> allNodeLists = nodeListsInAllSubgraphs.get(SG);
						HashMap<Integer, HashMap<Integer, Integer>> predecessors = predecessorsInAllSubgraphs.get(SG);
						HashMap<Integer, Integer> matchedVertexes = matched_vertexes_in_subgraph.get(SG);
						
						// record the predecessor of root on the shortest path from source to root
						predecessors.get(new Integer(vid)).put(R, new Integer(spv.getPredecessor()));
						
						// initialize the node lists for the vertex being visited first
						// time
						if (!allNodeLists.containsKey(R)) {
						ExpandableIntArray[] nodeLists = new ExpandableIntArray[groupNum];
						for (int i = 0; i < groupNum; i++) {
						nodeLists[i] = new ExpandableIntArray(4);
						//if (Arrays.binarySearch(matched_subgraph.getGroup(i), vid) >= 0) {
						//nodeLists[i].add(vid);
						//}
						}
						allNodeLists.put(R, nodeLists);
						}
						// make sure if there are answer trees rooted on this vertex
						for (int i = 0; i < groupNum; i++) {
						if (Arrays.binarySearch(matched_subgraph.getGroup(i), vid) >= 0) {
						HashSet<HashSet<Integer>> tuples = crossProduct(vid,
						i, allNodeLists.get(R));
						if (tuples != null) {
						Iterator<HashSet<Integer>> it2 = tuples.iterator();
						while (it2.hasNext()) {
						HashSet<Integer> tuple = it2.next();
						SimpleAnswer at = genAnswer(root, tuple,
						vid, predecessors);
						if (addTopKAnswer(at, size, topk)) {
						size++;
						}
						if (size == k) {
						return topk;
						}
						}
						}
						allNodeLists.get(R)[i].add(vid);
						}
						}
						// put this iterator back into the heap
						if (di.hasNext()) {
						iterator_heap.enqueue(di);
						}
					}
				}
				
				
				
				
			} catch (UnderflowException ex) {
				ex.printStackTrace();
			}

		}
		return null;
	}

	private HashSet<HashSet<Integer>> crossProduct(int vid, int i, ExpandableIntArray[] nodeLists) {
		HashSet<HashSet<Integer>> results = new HashSet<HashSet<Integer>>();
		HashSet<Integer> seed = new HashSet<Integer>();
		seed.add(new Integer(vid));
		results.add(seed);
		for (int j = 0; j < nodeLists.length; j++) {
			if (j != i) {
				if (nodeLists[j].getSize() == 0) {
					return null;
				}
				ArrayList<HashSet<Integer>> tuples = new ArrayList<HashSet<Integer>>();
				Iterator<HashSet<Integer>> it = results.iterator();
				while (it.hasNext()) {
					HashSet<Integer> tuple = it.next();
					it.remove();
					for (int k = 0; k < nodeLists[j].getSize(); k++) {
						int node = nodeLists[j].get(k);
						if (node == 0) {
							continue;
						}
						Integer n = new Integer(node);
						if (!tuple.contains(n)) {
							HashSet<Integer> newTuple = new HashSet<Integer>();
							newTuple.addAll(tuple);
							newTuple.add(n);
							tuples.add(newTuple);
						}
						else {
							tuples.add(tuple);
						}
					}
				}
				results.addAll(tuples);
			}
		}
		return results;
	}
	
	private SimpleAnswer genAnswer(int root, HashSet<Integer> tuple, 
			int origin, HashMap<Integer, HashMap<Integer, Integer>> allPredecessors) {
		Iterator<Integer> it = tuple.iterator();
		int[] leaves = new int[tuple.size()];
		int[][] paths = new int[tuple.size()][];
		SequentialIntArray allVertexes = new SequentialIntArray();
		allVertexes.insert(root);
		int i = 0;
		
		while (it.hasNext()) {
			leaves[i] = it.next().intValue();
			paths[i] = getPath(root, leaves[i], allVertexes, 
					allPredecessors.get(new Integer(leaves[i])));
			i++;
		}
		
		return new SimpleAnswer(root, leaves, paths, allVertexes.getArray());
	}

	private int[] getPath(int root, int vid, 
			SequentialIntArray allVertexes, HashMap<Integer, Integer> predecessors) {
		ExpandableIntArray eia = new ExpandableIntArray();
		int current = root;
		
		while (current != vid) {
			current = predecessors.get(new Integer(current)).intValue();
			if (current == 0) {
				return null;
			}
			allVertexes.insert(current);
			eia.add(current);
		}
		
		return eia.toArray();
	}

	private boolean addTopKAnswer(SimpleAnswer at, int size, SimpleAnswer[] topk) {
		for (int i = 0; i < size; i++) {
			int x = at.compare(topk[i]);
			if (x < 0) {
				return false;
			}
			else if (x > 0) {
//				System.out.println();
			}
		}
		topk[size] = at;
		return true;
	}

	private HashSet<SimpleSubgraphVertex> unionSubgraphVertexes() {
		HashSet<SimpleSubgraphVertex> result = new HashSet<SimpleSubgraphVertex>();
		matched_vertexes_in_subgraph = new HashMap<Integer, HashMap<Integer, Integer>>();
		Iterator<Integer> it = matched_subgraphs.keySet().iterator();
		while (it.hasNext()) {
			Integer I = it.next();
			HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
			SimpleMatchedSubgraph sms = matched_subgraphs.get(I);
			for (int j = 0; j < sms.groupNum(); j++) {
				for (int k = 0; k < sms.groupSize(j); k++) {
					SimpleSubgraphVertex sv = new SimpleSubgraphVertex(
							sms.getSubgraphID(),
							sms.getVertex(j, k));
					result.add(sv);
					Integer v = new Integer(sms.getVertex(j, k));
					if (map.containsKey(v)) {
						int num = map.remove(v).intValue();
						map.put(v, new Integer(num + 1));
					}
					else {
						map.put(v, new Integer(1));
					}
				}
			}
			matched_vertexes_in_subgraph.put(new Integer(sms
					.getSubgraphID()), map);
		}
		return result;
	}

}
